In order to test the PDDL code we wrote for each of our test domains, we needed to decide on a planner to use. We selected Fast-Forward (FF), because it was simple to compile and run on our systems, and it supported most of the features of PDDL we wanted to be able to take advantage of when encoding the test domains. Most of the information in this section comes from \cite{Hoffmann:2001fk}.

FF was the most successful automatic planner in the AIPS-2000 planning systems competition. However, the general idea behind FF was not new to the classical planning community - the basic principle is actually the same as that of the Heuristic Search Planner (HSP). FF executes a forward search in the state space, guided by a heuristic which is extracted from the domain description automatically. This function is extracted by relaxing the planning problem; a part of the specification (specifically, the delete lists of all actions) is ignored. 

There are a number of details in which FF is different from its predecessor, HSP:
\begin{enumerate}
    \item FF makes use of a more sophisticated method of heuristic evaluation, which takes into account positive interactions between facts.
    \item FF uses a different local search strategy; specifically, it is able to escape plateaus and local minima through the use of systematic search.
    \item FF includes a mechanism which identifies those successors of a search node which appear to be (and usually are) most helpful in achieving the goal. 
\end{enumerate}

The main difficulty which results from viewing domain independent planning as heuristic search is the automated derivation of the heuristic function. A common approach to this problem (which is adopted here) is to relax the general problem $\mathcal{P}$ into a simpler problem $\mathcal{P}^\prime$ which can be efficiently solved. Given a search state in the original problem, $\mathcal{P}$, the solution length of the same state $\mathcal{P}^\prime$ may be used to estimate the difficulty of $\mathcal{P}$. In \cite{Bonet:1997uq}, Bonet et al. propose a way to apply this idea to domain independent planning. In this paper, the high-level problem description is relaxed by ``ignoring'' delete lists. This means that in the relaxed problem, actions can only add new atoms to state - all negative literals in the effects of actions are ignored, and leave those literals in the state unchanged. As a result, states only grow (in terms of the number of literals present in the state) during execution of a sequence of such relaxed actions, and the problem is solved as soon as each goal literal has been added by some action. This relaxation can be used to derive heuristics that are informative on many benchmark domains in classical planning.

One such heuristic is the length of an optimal relaxed solution. This heuristic is admissible, and could be used to find optimal solution plans through application of $A^*$ search; however, computation of the length of an optimal relaxed solution is NP-hard \cite{Bylander:1994kx}. With this in mind, \cite{Bonet:1997uq} proposed a way of approximating relaxed solution length from a given search state $\mathcal{S}$, by computing weights over all facts which estimate their distance to $\mathcal{S}$. The key observation which lead to FF's heuristic method comes from \cite{Bylander:1994kx}: although computing optimal relaxed solution length is NP-hard, deciding relaxed solvability is actually in P. This means that there must exist polynomial-time decision algorithms, and if such an algorithm constructs a witness, that witness may be used for heuristic evaluation. One algorithmic method which accomplishes this is Graphplan, discussed in \cite{Blum:1997vn}. When applied to a solvable relaxed problem, Graphplan finds a solution in polynomial time. Facing a search state $\mathcal{S}$, therefore, FF runs a relaxed version of Graphplan starting at $\mathcal{S}$, and uses the resulting output for heuristic evaluation.

Although these heuristics can be computed in polynomial time, it is still costly to perform heuristic evaluation of states. A logical approach to this issue is to use hill-climbing as the search method, in order to attempt to reach the goal by evaluating as few states as possible. FF makes use of an enforced version of hill-climbing search. When facing a search state $\mathcal{S}$, FF evaluates all direct successors. If none of these successors has a better heuristic value than $\mathcal{S}$, the search then considers the next level (the successors' successors). Again, if none of the two-step successors looks better than $\mathcal{S}$, FF continues to the next level, and so on. This process ends when a state $\mathcal{S}^\prime$ which has a better heuristic evaluation than $\mathcal{S}$ is found. The path to $\mathcal{S}^\prime$ is then added to the current plan, and the search continues, starting at $\mathcal{S}^\prime$. If a planning problem does not contain dead end situations, this strategy is guaranteed to find a solution. 